package BinaryTreeProblem;


import sun.reflect.generics.tree.Tree;

import java.util.*;

public class BinaryTree {


    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }

    }

    protected TreeNode createTree() {
        TreeNode node1=new TreeNode('A');
       TreeNode node2=new TreeNode('B');
       TreeNode node3=new TreeNode('C');
       TreeNode node4=new TreeNode('D');
        TreeNode node5=new TreeNode('E');
        TreeNode node6=new TreeNode('F');

        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node6;
        return node1;
    }
/*
* 迭代法前序遍历二叉树
* */
    public List<Character> preorderTreeNode(TreeNode root){
        List<Character> result=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        if(root!=null){
            stack.push(root);
        }

        while(!stack.isEmpty()){
            TreeNode node=stack.peek();

            if(node!=null){
                stack.pop();

                if(node.right!=null){
                    stack.push(node.right);
                }
                if(node.left!=null){
                    stack.push(node.left);
                }
                stack.push(node);//把根节点放进去
                stack.push(null);//放完之后记录
            }else{
                stack.pop();//弹出的是null
                node=stack.pop();//弹出跟节点之后保存一下

                result.add(node.val);//保存到结果集中
            }
        }

        return result;
    }

    public List<Character> preorderTreeNode1(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        List<Character> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        TreeNode cur=root;

        while(cur!=null||!stack.isEmpty()){

            while(cur!=null){
                stack.push(root);
                list.add(root.val);
                cur=cur.left;
            }
            TreeNode top=stack.pop();//弹出元素
            cur=top.right;

        }
        return list;
    }
    /*
    * 中序迭代*/
    public List<Character> orderTreeNode(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        List<Character> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        TreeNode cur=root;
        TreeNode top=null;
        while(cur!=null||!stack.isEmpty()){

            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }//左边走完弹出元素
           top=stack.pop();//弹出元素
            list.add(cur.val);//弹出的记录一次下
            cur=top.right;
        }
        return list;
    }
//    后序遍历
    public List<Character> prosOrderTreeNode(TreeNode root){
        List<Character> list =new ArrayList<>();

        if(root==null){
            return  list;
        }
        TreeNode top1=null;
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null|| !stack.isEmpty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();//左边遍历完
            if(top.right==null||top.right==top1){//当右边也为空
                stack.pop();
                list.add(top.val);
                top1=top;//记录弹出的元素如果相等就进来弹出
            }else{
                cur=top.right;
            }

        }
        return list;

    }
   /* public TreeNode createTree(String str){
        Queue<TreeNode> queue=new LinkedList<>();
        Queue<TreeNode> queue1=new LinkedList<>();
        char[] ch= str.toCharArray();
        treeNode(ch,queue);//创造节点
        TreeNode cur=null;
      while(!queue.isEmpty()){
            int i=(int)Math.pow(2,0);
          while(!queue.isEmpty()&&i>0){
              cur=queue.poll();
              cur.Left=queue.poll();
              cur.right=queue.poll();
          }
      }

        return null;
    }
    public void treeNode(char[] chars,Queue<TreeNode> queue){
        int count=0;
        TreeNode cur=null;
        while(count<chars.length) {
            cur = new TreeNode(chars[count]);
            queue.offer(cur);
            count++;
        }

    }*/

}
